package tree.递归;

import po.TreeNode;

/**
 * @author songZiHao
 * @version 1.0.0
 * @ClassName N根据前序和后序遍历构造二叉树889.java
 * @Description https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal/
 * @createTime 2021年07月27日 19:15:00
 */
public class N根据前序和后序遍历构造二叉树889 {
	public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
		int preLength = preorder.length;
		int postLength = postorder.length;
		/**
		 * 后序遍历：  左子树为  post[post_start,index] 右子树为 post[index+1,post_end-1]   左子树的个数  index-post_start
		 * 前序遍历：  左子树为  pre[pre_start+1,index] , 结合前面后序遍历得到的左子树的个数。 pre[pre_start+1,index]= pre[pre_start+1,pre_start+1 + (index-post_start)]
		 *           右子树为  pre[index+1,pre_end] , 结合前面后序遍历得到的左子树的个数。 pre[index+1,pre_end]=pre[pre_start+1 + (index-post_start)+1,pre_end]
		 */
		return find(preorder,0,preLength-1,postorder,0,postLength-1);
	}

	private TreeNode find( int[] preorder,int preStart,int preEnd, int[] postorder,int postStart, int postEnd) {
		if (preStart>preEnd || postStart>postEnd){
			return  null;
		}
		//根节点
		TreeNode root = new TreeNode(preorder[preStart]);
		if (preStart == preEnd) {
			return root;
		}
		//在后续遍历中找到左子树结束的位置
		int index=postStart;
		while (preorder[preStart+1]!=postorder[index]){
			index++;
		}
		//左子树
		root.left=find(preorder,preStart+1,preStart+1+index-postStart,postorder,postStart,index);
		//右子树
		root.right = find(preorder,preStart+1+index-postStart+1,preEnd, postorder, index+1, postEnd-1);
		return root;
	}

}
